 |
|
There exist a variety of formulas for either producing the
nth prime as a function of n or taking on only prime
values. However, all such formulas require either extremely accurate
knowledge of some unknown constant, or effectively require knowledge
of the primes ahead of time in order to use the formula (Dudley
1969, Ribenboim 1996, p. 186). There also exist simple prime-generating
polynomials that exclusively primes exclusively for the first
(possibly large) number of integer values.
Considering examples of formulas that produce only prime numbers
(although not necessarily the complete set of prime numbers
P), there exists a constant  (Sloane's A051021)
known as Mills'
constant such that
 |
(1) | where  is the floor
function, is prime for all  (Ribenboim 1996, p. 186). The
first few values of f(n) are 2, 11, 1361, 2521008887,
... (Sloane's A051254).
It is not known if  is irrational.
There also exists a constant  such that
 |
(2) | (Wright 1951; Ribenboim 1996, p. 186) is prime
for every . The first few values of
g(n) are 3, 13, 16381, .... In the case of both
f(n) and g(n), the numbers at n =
4 grow so rapidly that an extremely precise value of or  is needed in order to obtain the
correct value, and values for  are effectively incomputable.
There follow a number of explicit formulas for explicitly
computing the nth prime. However, it should again be
emphasized that these formulas are extremely inefficient, and in
many (if not all) cases, simply performing an efficient sieving
would yield the primes much more quickly and efficiently. Explicit
formulas
exist for the nth prime both as a function of n and in
terms of the primes 2, ...,  (Hardy and Wright 1979,
pp. 5-6, 344-345, and 414; Guy 1994, pp. 36-41). Let
 |
(3) | for integral j > 1, where is again the floor
function. Then
where  is the prime
counting function. This formula conceals the prime numbers
j as those for which  , i.e., the values of
F(j) are 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, ....
Gandhi gave the formula in which  is the unique integer such that
 |
(6) | where  is the primorial
function (Gandhi 1971, Eynden 1972, Golomb 1974) and  is the Möbius
function. It is also true that
 |
(7) | (Ribenboim 1996, pp. 180-182). Note that the
number of terms in the summation to obtain the nth prime is
 , so these formulas turn out not to
be practical in the study of primes. An interesting infinite
product formula due to Euler that relates  and the nth prime  is
(Blatner 1997). Hardy and Wright (1979, p. 414) give
the formula
 |
(10) | for n > 3, where
 |
(11) | and an "elementary" formula for the prime
counting function is given by
 |
(12) | (correcting a sign error), where is the floor
function.
A double sum for the nth prime is
 |
(13) | where
 |
(14) | (Ruiz 2000).
B. M. Bredihin proved that
 |
(15) | takes prime values for infinitely many integral
pairs (x, y) (Honsberger 1976, p. 30). In addition, the
function
 |
(16) | where
 |
(17) |  is the factorial,
and is the floor
function, generates only prime numbers for positive
integer arguments. It not only generates every prime number, but
generates odd
primes exactly once each, with all other values being 2
(Honsberger 1976, p. 33). For example,
with no new primes generated for  .
The FRACTRAN game
(Guy 1983, Conway and Guy 1996, p. 147) provides an unexpected
means of generating the prime numbers based on 14 fractions, but it
is actually just a concealed version of a sieve.
 FRACTRAN, Mills'
Constant, Prime
Counting Function, Prime
Number, Sieve
References
Blatner, D. The
Joy of Pi. New York: Walker, p. 110, 1997.
Conway, J. H. and Guy, R. K. The
Book of Numbers. New York: Springer-Verlag, pp. 130 and
147, 1996.
Dudley, U. "History of Formula for Primes." Amer. Math.
Monthly 76, 23-28, 1969.
Finch, S. "Favorite Mathematical Constants." http://pauillac.inria.fr/algo/bsolve/constant/mills/mills.html.
Gandhi, J. M. "Formulae for the Nth Prime." Proc.
Washington State University Conferences on Number Theory.
pp. 96-107, 1971.
Gardner, M. "Patterns and Primes." Ch. 9 in The
Sixth Book of Mathematical Games from Scientific American.
Chicago, IL: University of Chicago Press, pp. 79-90, 1984.
Guy, R. K. "Conway's Prime Producing Machine." Math.
Mag. 56, 26-33, 1983.
Guy, R. K. "Prime Numbers," "Formulas for Primes," and
"Products Taken over Primes." Ch. A, §A17, and §B48 in Unsolved
Problems in Number Theory, 2nd ed. New York:
Springer-Verlag, pp. 3-43, 36-41, and 102-103, 1994.
Hardy, G. H. and Wright, E. M. "Prime Numbers" and "The
Sequence of Primes." §1.2 and 1.4 in An
Introduction to the Theory of Numbers, 5th ed. Oxford,
England: Clarendon Press, pp. 1-4, 5-6, 344-345, and 414, 1979.
Honsberger, R. Mathematical
Gems II. Washington, DC: Math. Assoc. Amer., 1976.
Mills, W. H. "A Prime-Representing Function." Bull. Amer.
Math. Soc. 53, 604, 1947.
Ribenboim, P. The
New Book of Prime Number Records. New York: Springer-Verlag,
1996.
Ruiz, S. M. "The General Term of the Prime Number Sequence
and the Smarandache Prime Function." Smarandache Notions J.
11, 59-61, 2000.
Sloane, N. J. A. Sequences A051021
and A051254
in "The On-Line Encyclopedia of Integer Sequences." http://www.research.att.com/~njas/sequences/.
Wright, E. M. "A Prime-Representing Function." Amer.
Math. Monthly 58, 616-618, 1951.
Author: Eric W. Weisstein
© 1999-2003 Wolfram Research, Inc.
|
